googologywikiaorg-20200223-history
User blog:Deedlit11/A rigorous definition for pentational arrays
Recently, we've been having some discussion of Bowers' pentational arrays. Bowers talks about pentational arrays briefly, but specific details are lacking. Here is my attempt at a rigorous definition of pentational array notation. Definition of pentational structures We define the set \(PE\) of pentational structure expressions as follows. \(PE\) is the smallest set such that 0, 1, X are in \(PE\). If f and g are in \(PE\), then f + g, f * g, \(X^f\), and \(X \uparrow \uparrow f\) are in \(PE\). Note that different expressions for pentational structures can express the same pentational structure. We define the equivalence relation ~ as follows. Given that f and g are in \(PE\): f + g ~ g + f f + 0 ~ f f * g ~ g * f f * 0 ~ 0 f * 1 ~ f \(X^0 \sim 1 \) \(X^1 \sim X \) \(X\uparrow\uparrow 0 \sim 1 \) \(X \uparrow\uparrow 1 \sim X\) \(X^{f + g} \sim (X^f) * (X^g) \) \(X^{X\uparrow \uparrow f} \sim X \uparrow\uparrow (f+1) \) ~ is the smallest equivalence relation that satisfies the above expressions. The set \(P\) of pentational structures is defined as the set \(PE\) modulo ~. That is, \(P\) is the set of pentational structure expressions where expressions that are related by ~ are considered the same structure. Ordering on pentational structures We need to order the pentational structures. For a pentational structure f, define N(f) to be the minimum number of symbols in an expression for f. We will define the comparsion between f and g by induction on max {N(f), N(g)}. Case 1: 0 < g is true for all g not equal to 0. Case 2: 1 < g is true for all g not equal to 0 or 1. Case 3: f < 0 is false for all f. Case 4: f < 1 is false unless f = 0. Case 5: At least one of f or g is the sum of two or more expressions. Let \(f = f_1 + f_2 + \ldots + f_m\) where \(f_1 \ge f_2 \ge \ldots \ge f_m\). (Note that \N(f_i) < \N(f)\) so we can assume by induction that comparisons for the \(f_i\) have already been defined.) Let \(g = g_1 + g_2 + \ldots + g_n\) where \(g_1 \ge g_2 \ge \ldots \ge g_n\). \(f < g \Leftrightarrow \exists i (f_i < g_i \wedge \forall j < i (f_j = g_j)) \vee (\forall i \le m (f_i = g_i) \wedge n > m) \). (In other words, we compare the summands term by term, starting from the largest, until we find a pair that are different. Whichever summand is greater will belong to the greater sum.) Case 6: At least one of f or g can be written as the product of two or more expressions. Let \(f = f_1 * f_2 * \ldots * f_m\) where \(f_1 \ge f_2 \ge \ldots \ge f_m\), and no \(f_i)\) is of the form \(X^{a+b}\) where a and b are nonzero. Let \(g = g_1 * g_2 * \ldots * g_n\) where \(g_1 \ge g_2 \ge \ldots \ge g_n\), and no \(g_i)\) is of the form \(X^{a+b}\) where a and b are nonzero. Then as before, \(f < g \Leftrightarrow \exists i (f_i < g_i \wedge \forall j < i (f_j = g_j)) \vee (\forall i \le m (f_i = g_i) \wedge n > m) \). Case 7: \(f = X^F, g = X^G\) \(f < g \Leftrightarrow F < G\). Case 8: \(f = X \uparrow\uparrow F, g = X \uparrow\uparrow G\) \(f < g \Leftrightarrow F < G\). Case 9: \(f = X^F, g = X \uparrow\uparrow G\) If \(F = X \uparrow \uparrow H\), then \(f < g \Leftrightarrow H+1 < G \). Otherwise, \(f < g \Leftrightarrow F < g\). Case 10: \(f = X \uparrow\uparrow F, g = X^G\) If \(G = X \uparrow \uparrow H\), then \(f < g \Leftrightarrow F < H+1 \). Otherwise, \(f < g \leftrightarrow f < G\). This completely defines the comparison relation. Standard form for pentational structures We define the standard form for a pentational array f. If f is a nontrivial sum, order the summands from largest to smallest, and express each summand in standard form. If f is of the form \(X^{g+h}\) express it in the form \((X^g) * (X^h) \), and express g and h in standard form. If f is a nontrivial product, order the factors from largest to smallest, and express each factor in standard form. If f is of the form \(X^{X\uparrow\uparrow f}\), express it in the form \(X \uparrow \uparrow (f+1) \), with f expressed in standard form. Fundamental sequences for pentational structures Given f expressed in standard form, define fn, the nth element of the fundamental sequence for f, as follows: If \(f = 0, fn = 0\). If \(f = g+1, fn = g\). If \(f = f_1 + f_2 + \ldots + f_m\), then \(fn = f_1 + f_2 + \ldots + f_mn\). If \(f = f_1 * f_2 * \ldots * f_m\), then \(fn = f_1 * f_2 * \ldots * f_mn\). If \(f = X^1\), \(fn = n \). If \(f = X^g\), \(fn = X^{gn} \). If \(f = X\uparrow\uparrow {g + 1}, fn = (X\uparrow\uparrow g)*(X\uparrow\uparrow g)* \ldots *(X\uparrow\uparrow g)\), where there are n terms in the product. If \(f = X\uparrow\uparrow g\) and g is not of the form h+1, then \(fn = X\uparrow\uparrow (gn)\). Prime blocks for pentational structures We will use the same definition for the prime blocks as used by FB100Z in his Ordinal BEAF notation. Call f a successor pentational structure if f is of the form g+1 for some g. Call f a limit pentational structure if f is neither a successor pentational structure nor 0. Define \(P_p (\alpha) \), the prime block of \(\alpha\), as follows: \(P_p(0) = \lbrace \rbrace\). \(P_p(f + 1) = \lbrace f \rbrace \cup P_p (f) \). If f is a limit pentational structure, \(P_p (f) = P_p (fp)\). Pentational Arrays Having defined prime blocks for pentational structures, we are now ready to define pentational arrays. A pentational array is a map from pentational structures to the natural numbers; we can notate this as \(\lbrace (\alpha_1, n_1), (\alpha_2, n_2), \ldots, (\alpha_m, n_m) \rbrace\), where the \(\alpha_i\) are increasing. The 0 structure will map to the base number, and the 1 structure will map to the prime number. The pilot P will be the smallest structure greater than 1 mapping to a positive number, and the copilot CP will be the structure such that P = CP+1, if such a structure exists. The definition of BEAF is the usual one. Hopefully there are no major mistakes, and we have successfully defined pentational arrays. Relationship between structures and ordinals In the following, A will stand for an arbitrary structure with corresponding ordinal \(\alpha\). Category:Blog posts